package com.lw.leetcode.sort.c;

import java.util.Arrays;
import java.util.TreeSet;

/**
 * Created with IntelliJ IDEA.
 * 1847. 最近的房间
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/10 10:24
 */
public class ClosestRoom {

    public int[] closestRoom(int[][] rooms, int[][] queries) {
        int m = rooms.length;
        int n = queries.length;
        int[][] arr = new int[n][3];
        for (int i = 0; i < n; i++) {
            arr[i][0] = queries[i][0];
            arr[i][1] = queries[i][1];
            arr[i][2] = i;
        }
        int[] values = new int[n];
        Arrays.sort(rooms, (a, b) -> Integer.compare(b[1], a[1]));
        Arrays.sort(arr, (a, b) -> Integer.compare(b[1], a[1]));
        int t = 0;
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            int[] ints = arr[i];
            int id = ints[0];
            int size = ints[1];
            int index = ints[2];
            while (t < m && rooms[t][1] >= size) {
                set.add(rooms[t][0]);
                t++;
            }
            int v = -1;
            Integer floor = set.floor(id);
            Integer ceiling = set.ceiling(id);
            if (floor != null) {
                v = floor;
            }
            if (ceiling != null) {
                if (floor == null) {
                    v = ceiling;
                } else {
                    v = ceiling + floor < (id << 1) ? ceiling : floor;
                }
            }
            values[index] = v;
        }
        return values;
    }

}
